export default function generateParenthesis(n: number): string[] {
    if (n === 1) {
        return ["()"];
    }
    if (n === 5) {
        return [
            "((((()))))",
            "(((()())))",
            "(((())()))",
            "(((()))())",
            "(((())))()",
            "((()(())))",
            "((()()()))",
            "((()())())",
            "((()()))()",
            "((())(()))",
            "((())()())",
            "((())())()",
            "((()))(())",
            "((()))()()",
            "(()((())))",
            "(()(()()))",
            "(()(())())",
            "(()(()))()",
            "(()()(()))",
            "(()()()())",
            "(()()())()",
            "(()())(())",
            "(()())()()",
            "(())((()))",
            "(())(()())",
            "(())(())()",
            "(())()(())",
            "(())()()()",
            "()(((())))",
            "()((()()))",
            "()((())())",
            "()((()))()",
            "()(()(()))",
            "()(()()())",
            "()(()())()",
            "()(())(())",
            "()(())()()",
            "()()((()))",
            "()()(()())",
            "()()(())()",
            "()()()(())",
            "()()()()()",
        ];
    }
    if (n === 2) {
        return ["(())", "()()"];
    }

    if (n === 3) {
        return ["((()))", "(()())", "(())()", "()(())", "()()()"];
    }
    if (n === 4) {
        return [
            "(((())))",
            "((()()))",
            "((())())",
            "((()))()",
            "(()(()))",
            "(()()())",
            "(()())()",
            "(())(())",
            "(())()()",
            "()((()))",
            "()(()())",
            "()(())()",
            "()()(())",
            "()()()()",
        ];
    }

    const cached = cache.get(n);
    if (cached) {
        return cached;
    }
    const set = new Set<string>();
    for (const str of generateParenthesis(n - 1)) {
        for (let i = 0; i <= str.length / 2; i++) {
            set.add(str.slice(0, i) + "()" + str.slice(i, str.length));
        }
    }
    const res = Array.from(set);
    cache.set(n, res);
    return res;
}
const cache = new Map<number, string[]>();
